package OptimalAlgorithm.SlidingWindow;

//给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。
//请注意，需要 修改 数组以供接下来的操作使用。
//如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
//eg：
//输入：nums = [1,1,4,2,3], x = 5
//输出：2
//解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

//将问题转换为：找到最长的子数组使得 总数组和 - 子数组和 = x
public class MinOperations {
    public int minOperations(int[] nums, int x) {
        int totalSum = 0;
        for (int i = 0; i < nums.length; i++) {
            totalSum += nums[i];
        }
        int len = -1;
        int target = totalSum - x;
        if(target < 0) {
            return -1;
        }
        int total = 0;
        for(int left = 0,right = 0;right < nums.length;right++){

            total += nums[right];
            while (total > target){
                total -= nums[left];
                left++;
            }
            if(total == target) {
                len = Math.max(len, right - left + 1);
            }
        }
        if(len == -1){
            return -1;
        }else {
            return nums.length - len;
        }
    }
}
